package com.tys.algorithm.advanced.code.class06;

import java.util.Arrays;
import java.util.PriorityQueue;

/**
 * 排序：已知一个几乎有序的数组，
 * 几乎有序：如果吧数组排好序的话，每个元素移动的距离移动不超过K，
 * 并且K相对于数组长度来说是比较小的，选择一个合适的排序策略，对这个数组进行排序
 * <p>
 * 0-K范围之后的不能比0-K范围内的数小，因为有限制条件
 */
public class Code04_SortArrayDistanceLessK {

    /**
     * 使用优先级队列的小根堆
     *
     * @param arr 几乎有序数组，无序数组
     * @param k   排序移动的最大距离
     */
    public static void sortedArrDistanceLessK(int[] arr, int k) {
        if (arr == null || arr.length < 2) {
            return;
        }

        //不要排序
        if (k == 0) {
            return;
        }

        // 小根堆的优先级队列，借助优先级队列，使用默认的小根堆
        PriorityQueue<Integer> heap = new PriorityQueue<>();
        //当前数组位置
        int index = 0;
        //将前k个数加到优先级队列中，如果总数没有K个则就加当前有的
        // 0...K-1
        for (; index <= Math.min(arr.length - 1, k - 1); index++) {
            heap.add(arr[index]);
        }
        //排序位置
        //从第k+1个开始，加一个到优先级队列，并且弹一个出来到数组中
        int i = 0;
        for (; index < arr.length; index++) {
            heap.add(arr[index]);//加入小根堆
            arr[i++] = heap.poll();//弹出最小值到数组，数已经在堆中可以覆盖arr前面的数
        }
        //将堆中最后剩余的数全部弹出放入到数组
        while (!heap.isEmpty()) {
            arr[i++] = heap.poll();
        }
    }

    //测试：调用系统排序
    public static void comparator(int[] arr, int k) {
        Arrays.sort(arr);
    }

    /**
     * 随机产生几乎有序数组
     *
     * @param maxSize  最大长度
     * @param maxValue 最大值
     * @param K        排序移动距离
     * @return 几乎有序数组
     */
    public static int[] randomArrayNoMoveMoreK(int maxSize, int maxValue, int K) {
        //建立数组
        int[] arr = new int[(int) ((maxSize + 1) * Math.random())];
        //放入随机数
        for (int i = 0; i < arr.length; i++) {
            arr[i] = (int) ((maxValue + 1) * Math.random()) - (int) (maxValue * Math.random());
        }

        //先排个序，调用系统排序
        Arrays.sort(arr);
        //随机交换标记数组，然后开始随意交换，但是保证每个数距离不超过K
        //swap[i]=true，表示i位置已经参与过交换，false则表示没有
        // swap[i] == true, 表示i位置已经参与过交换
        // swap[i] == false, 表示i位置没有参与过交换
        boolean[] isSwap = new boolean[arr.length];
        //交换数组中元素
        for (int i = 0; i < arr.length; i++) {
            //随机0-k，k如果大于数组长度则取数组长度
            int j = Math.min(i + (int) (Math.random() * (K + 1)), arr.length - 1);
            //交换并设置标记位
            if (!isSwap[i] && !isSwap[j]) {
                isSwap[i] = true;
                isSwap[j] = true;
                int tmp = arr[i];
                arr[i] = arr[j];
                arr[j] = tmp;
            }
        }
        return arr;
    }

    //拷贝数组
    public static int[] copyArray(int[] arr) {
        if (arr == null) {
            return null;
        }
        int[] res = new int[arr.length];
        for (int i = 0; i < arr.length; i++) {
            res[i] = arr[i];
        }
        return res;
    }

    //对比数组是否相等
    public static boolean isEqual(int[] arr1, int[] arr2) {
        if ((arr1 == null && arr2 != null) || (arr1 != null && arr2 == null)) {
            return false;
        }
        if (arr1 == null && arr2 == null) {
            return true;
        }
        if (arr1.length != arr2.length) {
            return false;
        }
        for (int i = 0; i < arr1.length; i++) {
            if (arr1[i] != arr2[i]) {
                return false;
            }
        }
        return true;
    }

    //打印数组
    public static void printArray(int[] arr) {
        if (arr == null) {
            return;
        }
        for (int i = 0; i < arr.length; i++) {
            System.out.print(arr[i] + " ");
        }
        System.out.println();
    }

    public static void main(String[] args) {
        System.out.println("test begin");
        int testTime = 500000;
        int maxSize = 100;
        int maxValue = 100;
        boolean succeed = true;
        for (int i = 0; i < testTime; i++) {
            int k = (int) (Math.random() * maxSize) + 1;
            int[] arr = randomArrayNoMoveMoreK(maxSize, maxValue, k);
            int[] arr1 = copyArray(arr);
            int[] arr2 = copyArray(arr);
            sortedArrDistanceLessK(arr1, k);
            comparator(arr2, k);
            if (!isEqual(arr1, arr2)) {
                succeed = false;
                System.out.println("K:" + k);
                printArray(arr);
                printArray(arr1);
                printArray(arr2);
                break;
            }
        }
        System.out.println(succeed ? "Nice!" : "Fucking fucked!");
    }
}